The EVAL and APPLY operations form the core of a Lisp interpreter and are fundamental to implementations of applicative languages in general. One of the more difficult tasks in teaching Lisp to beginners is getting them to understand the true nature of the EVAL/APPLY duality. With the advent of Scheme [3] and Common Lisp [4], even experienced Lisp programmers may find that they don't fully understand evaluation, especially as it relates to lexical vs. dynamic scoping, closures, local and special variables, and macro expansion.
In this article we present a technique for visualizing evaluation in applicative languages that helps to graphically explain each of the above concepts. Called ``evaltrace notation,'' it appears in a recent textbook by the first author [5] and has been employed in several courses at Carnegie Mellon. Although our discussion in this paper focuses primarily on the notation itself, we also provide some insights into the implementation of Lisp and Scheme interpreters and the differences between the lexical and dynamic scoping disciplines. Extensions to other features such as tail-recursion elimination and first-class continuations are quite easy to make, though we do not include them here. It is our hope that evaltrace notation will be widely adopted by Lisp educators. In support of this, we are making available a set of LATEX macros to allow others to produce evaltrace diagrams similar to the ones that appear here.